//大餐 是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。 
//
// 你可以搭配 任意 两道餐品做一顿大餐。 
//
// 给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 大
//餐 的数量。结果需要对 109 + 7 取余。 
//
// 注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。 
//
// 
//
// 示例 1： 
//
// 
//输入：deliciousness = [1,3,5,7,9]
//输出：4
//解释：大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。
//它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。
// 
//
// 示例 2： 
//
// 
//输入：deliciousness = [1,1,1,3,3,3,7]
//输出：15
//解释：大餐的美味程度组合为 3 种 (1,1) ，9 种 (1,3) ，和 3 种 (1,7) 。 
//
// 
//
// 提示： 
//
// 
// 1 <= deliciousness.length <= 105 
// 0 <= deliciousness[i] <= 220 
// 
// Related Topics 数组 哈希表 


import java.util.*;

public class Leetcode1711 {

    // 计算每个数字的差值，取前面Map中出现的该值的数量累加；
	public int countPairs(int[] deliciousness) {
        Map<Integer, Integer> map = new HashMap<>();
        long res = 0l;
        for (int num : deliciousness) {
        	System.out.println(num + ":" +map);
            int powOfTwo = 1;
            for (int i = 0; i <= 21; i++) {
                if (powOfTwo >= num) {
                	Integer n = map.get(powOfTwo - num);
                	if(n!=null){
                		res += n;
                		System.out.println(num+ " + " + (powOfTwo - num) +" = " + powOfTwo);
                	}
                }
                powOfTwo <<= 1;
            }
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        return (int) (res % 1000000007);
    }

    // 暴力法
    public int countPairs2(int[] deliciousness) {
    	int res = 0;
        for (int i=1;i<deliciousness.length;i++) {
            for (int j = 0;j<i;j++) {
            	if(isPowOfTwo(deliciousness[i]+deliciousness[j])){
            		res++;
        			System.out.println(deliciousness[i]+ " + " + deliciousness[j] +" = " + (deliciousness[i]+deliciousness[j]));
            	}
            }
        }
        return (int) (res % 1000000007);
    }

    public boolean isPowOfTwo(int num){
		int powOfTwo = 1;
		for (int i = 0; i <= 21; i++) {
			if (powOfTwo == num) {
				return true;
			}
			powOfTwo <<= 1;
		}
		return false;
    }

    // 计算每个数字的差值，取前面数组中出现的该值的数量累加；
    public int countPairs3(int[] deliciousness){
    	int min = deliciousness[0], max = deliciousness[0];
        for (int num : deliciousness) {
            if (num < min) {
                min = num;
            }
            if (num > max) {
                max = num;
            }
        }

        int[] map = new int[max - min + 1];
        int ret = 0;
        for (int num : deliciousness) {
            for (int i = 1; ; i <<= 1) {
                int j = i - num;
                if (j < min) continue;
                if (j > max) break;
                ret += map[j - min];
            }
            map[num - min]++;
        }
        return (int) (ret % 1000000007);
    }
}